package backtrack;

import java.util.LinkedList;
import java.util.List;

/**
 * 学习回溯算法
 * @author gaolaina
 */
public class LearnBacktrack
{
    private static List<List<Integer>> res = new LinkedList<>();

    public static void main(String[] args)
    {
        int[] nums = {1, 1, 2};
        boolean[] used = new boolean[nums.length];
        LinkedList<Integer> tmp = new LinkedList<>();
        backtrack(nums, tmp, used);

        for (int i = 0;i < res.size();i++){
            System.out.println(res.get(i).toString());
        }
    }

    private static void backtrack(int[] nums ,LinkedList<Integer> tmp, boolean[] used){
        if (tmp.size() == nums.length){
             res.add(new LinkedList<>(tmp));
            return;
        }
        for (int i = 0;i < nums.length;i++){
            if (used[i]){
                continue;
            }
            tmp.add(nums[i]);
            used[i] = true;
            backtrack(nums, tmp, used);
            tmp.removeLast();
            used[i] = false;
        }
    }
}
